#include <iostream>
#include <vector>
using namespace std;

class WordDictionary
{
private:
    vector<WordDictionary *> children;
    bool end;

public:
    WordDictionary()
    {
        children.resize(26);
        end = false;
    }

    void addWord(string word)
    {
        if (word.empty())
        {
            end = true;
            return;
        }
        int ids = word[0] - 'a';
        if (children[ids] == nullptr)
        {
            children[ids] = new WordDictionary();
        }
        children[ids]->addWord(string(word.begin() + 1, word.end()));
    }

    bool search(string word)
    {
        if (word.empty())
        {
            return end;
        }
        if (word[0] == '.')
        {
            for (auto child : children)
            {
                if (child != nullptr && child->search(string(word.begin() + 1, word.end())))
                {
                    return true;
                }
            }
            return false;
        }
        else
        {
            int ids = word[0] - 'a';
            if (children[ids] == nullptr)
            {
                return false;
            }
            return children[ids]->search(string(word.begin() + 1, word.end()));
        }
    }
};

int main()
{
    cout << "Code211" << endl;
    WordDictionary wordDictionary = WordDictionary();
    cout << boolalpha;
    wordDictionary.addWord("at");
    wordDictionary.addWord("and");
    wordDictionary.addWord("add");
    wordDictionary.addWord("an");
    cout << wordDictionary.search(".at") << endl; // 返回 False
    cout << wordDictionary.search("a") << endl; // 返回 True
    wordDictionary.addWord("bat");
    cout << wordDictionary.search(".at") << endl; // 返回 True
    cout << wordDictionary.search("an.") << endl; // 返回 True
    cout << wordDictionary.search("a.d.") << endl; // 返回 True
    cout << wordDictionary.search("b.") << endl; // 返回 True
    cout << wordDictionary.search("a.d") << endl; // 返回 True
    cout << wordDictionary.search(".") << endl; // 返回 True
    return 0;
}